|
In parallel computing, the fork–join model is a way of setting up and executing parallel programs, such that execution branches off in parallel at designated points in the program, to "join" (merge) at a subsequent point and resume sequential execution. Parallel sections may fork recursively until a certain task granularity is reached. Fork–join can be considered a parallel design pattern. It was formulated as early as 1963. By nesting fork–join computations recursively, one obtains a parallel version of the divide and conquer paradigm, expressed by the following generic pseudocode: solve(problem): if problem is small enough: solve problem directly (sequential algorithm) else: for part in subdivide(problem) fork subtask to solve part join all subtasks spawned in previous loop combine results from subtasks == Examples == The simple parallel merge sort of CLRS is a fork–join algorithm. mergesort(A, lo, hi): if lo < hi: ''// at least one element of input'' mid = ⌊(hi - lo) / 2⌋ fork mergesort(A, lo, mid) ''// process (potentially) in parallel with main task'' mergesort(A, mid, hi) ''// main task handles second recursion'' join merge(A, lo, mid, hi) The first recursive call is "forked off", meaning that its execution may run in parallel (in a separate thread) with the following part of the function, up to the that causes all threads to synchronize. While the may look like a barrier, it is different because the threads will continue to work after a barrier, while after a only one thread continues. The second recursive call is not a fork in the pseudocode above; this is intentional, as forking tasks may come at an expense. If both recursive calls were set up as subtasks, the main task would not have any additional work to perform before being blocked at the .〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fork–join model」の詳細全文を読む スポンサード リンク
|